# -*- coding: utf-8 -*-

"""剑指 Offer II 117. 相似的字符串
如果交换字符串 X 中的两个不同位置的字母，使得它和字符串 Y 相等，那么称 X 和 Y 两个字符串相似。如果这两个字符串本身是相等的，那它们也是相似的。
例如，"tars" 和 "rats" 是相似的 (交换 0 与 2 的位置)； "rats" 和 "arts" 也是相似的，但是 "star" 不与 "tars"，"rats"，或 "arts" 相似。
总之，它们通过相似性形成了两个关联组：{"tars", "rats", "arts"} 和 {"star"}。注意，"tars" 和 "arts" 是在同一组中，即使它们并不相似。形式上，对每个组而言，要确定一个单词在组中，只需要这个词和该组中至少一个单词相似。
给定一个字符串列表 strs。列表中的每个字符串都是 strs 中其它所有字符串的一个 字母异位词 。请问 strs 中有多少个相似字符串组？
字母异位词（anagram），一种把某个字符串的字母的位置（顺序）加以改换所形成的新词。

示例 1：
输入：strs = ["tars","rats","arts","star"]
输出：2

示例 2：
输入：strs = ["omv","ovm"]
输出：1

提示：
1 <= strs.length <= 300
1 <= strs[i].length <= 300
strs[i] 只包含小写字母。
strs 中的所有单词都具有相同的长度，且是彼此的字母异位词。"""

class Solution:
    """按通常来看，这个题应该先遍历所有的两两组合字符串，形成图结构，然后再从这个图上做文章，数数有几个连通图。
    不过本体只需要知道有几个连通图，并不需要获知具体的连通图，所以用并查集会是一种很好的方法。
    
    用一个列表等长数组，各个位置的值代表该位置的元素所在的集合或连通图，即是有这个结构的元素都有关系。
    [0, 1, 2, 3]为初始状态，表示，它们各自独立，[1, 1, 2, 3]表示第0号元素所在的集合与第1号元素一致。
    最终的结果就是，如果某个位置的集合表示有变动，就代表他与指向的元素在一个集合；只有位置跟值一致（没有变动过），表示这就是一个集合的原点"""
    def numSimilarGroups(self, strs: list) -> int:
        size, length = len(strs), len(strs[0])
        dsu = list(range(size))

        def check(wordi, wordj):
            count, xy = 0, []
            p = 0
            while p < length:
                if count > 2:
                    return False
                if wordi[p] != wordj[p]:
                    count += 1
                    xy.extend([wordi[p], wordj[p]])
                p += 1

            if count == 0:
                return True

            if count == 2 and xy[0] == xy[3] and xy[1] == xy[2]:
                return True

        def find(i):
            if dsu[i] == i:
                return i
            dsu[i] = find(dsu[i])
            return dsu[i]

        i = 0
        while i < size-1:
            j = i + 1
            while j < size:
                if check(strs[i], strs[j]):
                    dsu[find(j)] = find(i)
                    dsu[j] = find(i)
                j += 1
            i += 1

        i, count = 0, 0
        while i < size:
            if i == dsu[i]:
                count += 1
            i += 1

        return count


if __name__ == '__main__':
    print(Solution().numSimilarGroups(["tars","rats","arts","star"]))
    print(Solution().numSimilarGroups(["omv","ovm"]))
